package com.ywk.base.dataStructure.queue;

import java.util.Scanner;

//rear指针与front指针在同一个位置时，表示队满，因为rear始终指的是队尾的后一个位置
//（即还没有添加值得地方），当队列添加满了之后，此时的rear通过加1取模之后指针与
//front指针在同一位置，因此需要通过过预留一个空间，来错开这种情况（即：maxSize-1才是队列真实的容量）
public class CircleQueueDemo {

	public static void main(String[] args) {
		CircleQueue c=new CircleQueue(4);
		char key;
		Scanner input=new Scanner(System.in);
		boolean loop=true;
		int data;
		while(loop) {
			System.out.println("s(show):显示队列");
			System.out.println("e(exit):退出程序");
			System.out.println("a(add):添加队列数据");
			System.out.println("g(get):取出队列数据");
			System.out.println("h(head):查看队列头数据");
			System.out.print("请选择：");
			key=input.next().charAt(0);
			
			switch (key) {
			case 's':
				try {
					c.showQueue();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				input.close();
				loop=false;
				break;
			case 'a':
				System.out.print("添加数据：");
				data=input.nextInt();
				c.addQueue(data);
				break;
			case 'g':
				try {
					int value=c.getQueue();
					System.out.printf("取出的数据:%d\n",value);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					c.headQueue();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			default:
				break;
			}
		}
		System.out.println("程序已退出");
	}

}

class CircleQueue{
	private int maxSize;
	private int rear;//队尾（不包含），初值为0(已经是默认值了)
	private int front;//对头（包含），初值为0(已经是默认值了)
	private int[] circleQ;
	
	public CircleQueue(int maxSize) {
		this.maxSize=maxSize;
		circleQ=new int[this.maxSize];
	}
	
	public boolean isFull() {
		return (rear+1)%maxSize==front;
	}
	
	public boolean isEmpty() {
		return rear==front;
	}
	
	public void addQueue(int data) {
		if(isFull()) {
			System.out.println("队列已满，不能添加了...");
			return;
		}
		circleQ[rear]=data;
		rear=(rear+1)%maxSize;
	}
	
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空...");
		}
		//因为返回的值是front指针后移之前的值，因此将该值放到一个
		//临时变量来返回，再后移front指针(即：先取值再移指针)
		int value=circleQ[front];
		front=(front+1)%maxSize;
		return value;
	}
	
	public void showQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空...");
		}
		for (int i = front; i < front+DataSize(); i++) {
			//因为i的取值有可能超出边界，所以的取模
			System.out.printf("队列第%d个数：%d\n",i%maxSize,circleQ[i%maxSize]);
			
		}
	}
	
	//注重循环时候涉及的算法：取模
	public int DataSize() {
		return (rear+maxSize-front)%maxSize;//举个短小的例子，列出至少3种可能，从中找出规律
	}
	
	public void headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空...");
		}
		System.out.printf("队列的头信息：%d\n",circleQ[front]);
	}
	
}
